/*
 * @lc app=leetcode.cn id=146 lang=cpp
 * @lcpr version=30204
 *
 * [146] LRU 缓存
 */


// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class LRUCache {
    // 这个类的本质是先需要查找，而查找里可以达到O（1）的是哈希 ，查找完后就是更新，需要进行插入、删除
    // 而插入、删除为O（1）的是list，但是不知道位置的话需要先找到那么又回到了O（N）
    // 这个时候就需要在哈希表中存储list中数据的位置，那就需要key/value哈希表
public:
    LRUCache(int capacity) {
        _capacity = capacity;
    }
    
    int get(int key) {
        auto ret = _hashmap.find(key);
        if(ret != _hashmap.end())
        {
            auto pos = ret->second;
            auto kv = *pos;
            _lrulist.erase(pos);
            _lrulist.push_front(kv);
            _hashmap[key] = _lrulist.begin();
            return kv.second;
        }
        else
        {
            return -1;
        }
    }
    
    void put(int key, int value) {
        // 判断插入还是更新
        auto ret = _hashmap.find(key);
        if(ret != _hashmap.end())
        {
            // 找到了，准备更新
            auto pos = ret->second;
            _lrulist.erase(pos);
            _lrulist.push_front(make_pair(key,value));
            _hashmap[key] = _lrulist.begin();
        }
        else
        {
            // 没找到，需要插入
            // 1、满了
            if(_lrulist.size() == _capacity)
            {
                auto back = _lrulist.back();
                _hashmap.erase(back.first);
                _lrulist.pop_back();
            }
            // 2、没满
            _lrulist.push_front(make_pair(key,value));
            _hashmap.insert(make_pair(key,_lrulist.begin()));
        }


    }
private:
    unordered_map<int,list<pair<int,int>>::iterator> _hashmap;
    list<pair<int,int>> _lrulist;
    int _capacity;
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */
// @lc code=end



